package com.algorithm.array;

public class CaptureRain {
    /**
     *@author : daniel.yang
     *@date : 2018/11/12
     *@desc : 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
     *@param null :
     *
     */
    /**
     * 8                                          @@@@@@
     * 8                                          @@@@@@
     * 8                                          @@@@@@
     * 8                  @@@@@@******************@@@@@@@@@@@@******@@@@@@
     * 8                  @@@@@@******************@@@@@@@@@@@@******@@@@@@
     * 8                  @@@@@@******************@@@@@@@@@@@@******@@@@@@
     * 8      @@@@@@******@@@@@@@@@@@@******@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 8      @@@@@@******@@@@@@@@@@@@******@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 8      @@@@@@******@@@@@@@@@@@@******@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     */
    public static void main(String[] args) {
        int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int length = arr.length;
        int[] topIndexs = new int[length];

        int topSize = 0;

        if (arr[0] > arr[1]) {
            topIndexs[topSize++] = 0;
        }
        if (arr[length - 1] > arr[length - 2]) {
            topIndexs[topSize++] = length - 1;
        }
        for (int i = 1; i < length - 1; i++) {
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                topIndexs[topSize++] = i;
            }
        }

        int index = 0;
        int preTopIndex = topIndexs[index];
        int postTopIndex = topIndexs[index+1];
        int low = arr[preTopIndex] >= arr[postTopIndex] ? arr[postTopIndex] : arr[preTopIndex];
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i > preTopIndex) {
                int thisCol = (low - arr[i]) > 0 ? low - arr[i] : 0;
                sum += thisCol;
            }
            if (i == postTopIndex -1) {
                index ++;
                preTopIndex = topIndexs[index];
                postTopIndex = topIndexs[index + 1];
                low = arr[preTopIndex] >= arr[postTopIndex] ? arr[postTopIndex] : arr[preTopIndex];
                if (preTopIndex == 0) break;
            }
        }
        System.out.println(sum);
    }
}
